from __future__ import division

import math
import random

import graph
import map

def generate_map(width, height, gridsize):
    nodes = {}
    
    yoff = math.cos(math.radians(30))*gridsize
    
    for y in xrange(height):
        if y % 2:
            xoff = gridsize / 2
        else:
            xoff = 0
        
        for x in xrange(width):
            nodes[x, y] = graph.Node((int(x*gridsize + xoff), int(yoff*y)))
    
    for y in xrange(height):
        for x in xrange(width):
            a = nodes[(x, y)]
            
            if y < height - 1:
                a.link(nodes[(x, y + 1)])
            if x < width - 1:
                a.link(nodes[(x + 1, y)])
                
            if x >= 1 and y < height - 1 and y % 2 == 0:
                nodes[x-1, y+1].link(a)
            
            if y >= 1 and x < width - 1 and y < height - 1 and y % 2 == 1:
                nodes[x+1, y+1].link(a)
    
    reverses = {value: key for key, value in nodes.iteritems()}
    
    for i in xrange(height * width // 50):
        x = random.randint(1, width-2)
        y = random.randint(1, height-2)
        
        while not (x, y) in nodes:
            x = random.randint(1, width-2)
            y = random.randint(1, height-2)
        
        node = nodes[x, y]
        
        for i in xrange(15):
            if not node.neighbours:
                break
            
            tried = set()
            
            new = random.choice(list(node.neighbours))
            tried.add(new)
            
            x, y = reverses[new]
            
            while (x == 0 or y == 0 or x >= width-2 or y >= height-2) and set(node.neighbours) - tried:
                new = random.choice(list(node.neighbours - tried))
                tried.add(new)
                
                x, y = reverses[new]
            
            if (x == 0 or y == 0 or x >= width-2 or y >= height-2):
                break
            
            for neighbour in set(node.neighbours):
                neighbour.unlink(node)

            del nodes[reverses[node]]
            node = new
    
    prob = (True,)# False, False, False, False, False)
    
    spawns = set(nodes[x, 0] for x in xrange(width) if random.choice(prob))
    spawns |= set(nodes[x, height-1] for x in xrange(width) if random.choice(prob))
    spawns |= set(nodes[0, y] for y in xrange(height) if random.choice(prob))
    spawns |= set(nodes[width-1, y] for y in xrange(height) if random.choice(prob))
    
    objective = random.choice([nodes[x, y] for x in xrange(50, width - 50) for y in xrange(50, height - 50) if nodes.has_key((x, y))])
    
    pathgraph = graph.Graph(set(node for node in nodes.itervalues()))
    
    pathgraph.trim(nodes[0, 0])
    
    for node in set(pathgraph.nodes):
        if not node.neighbours:
            pathgraph.nodes.remove(node)
    
    gamemap = map.Map(objective, spawns, pathgraph)
    
    return gamemap